package 剑指专题.链表;


/*
 * Author：江松
 * Date：2023/3/26 12:33
 *
 复杂链表的复制:
 1,哈希表<old,clone>
 */

import java.util.HashMap;
import java.util.Map;

public class Main8 {
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead) {
        HashMap<RandomListNode,RandomListNode>map=new HashMap<>();
        RandomListNode now=pHead;
        RandomListNode head=new RandomListNode(0);
        head.next=pHead;
        //用尾插法创建新链表
        RandomListNode pre=head;
        while(now!=null){
            RandomListNode clone=new RandomListNode(now.label);
            map.put(now,clone);
            pre.next=clone;
            pre=clone;
            now=now.next;
        }
        for(Map.Entry<RandomListNode,RandomListNode>entry:map.entrySet()){
            if(entry.getKey().random==null){
                entry.getValue().random=null;
            }else{
                //原来的random对应的克隆中的random
                entry.getValue().random=map.get(entry.getKey().random);
            }
        }
        return head.next;
    }
}
